package com.faiz.algorithm;




public class FlattenTree {
    private static final String NULL = "null";

    private static final String SEPARATOR = ",";

    // 使用递归的方法解决问题
    public void flatten(TreeNode root) {
        if (root == null) return;
        // 将左右子树拉平
        flatten(root.left);
        flatten(root.right);

        TreeNode left = root.left;
        TreeNode right = root.right;
        // 将左右子树拉平

        root.right = left;
        root.left = null;

        TreeNode tmp = root;

        while (tmp.right != null) tmp = tmp.right;
        tmp.right = right;


    }

    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        serialize(root, sb);
        return sb.deleteCharAt(sb.length() - 1).toString();
    }

    private void serialize(TreeNode root, StringBuilder sb) {
        if (root == null) {
            sb.append(NULL).append(SEPARATOR);
            return;
        }

        sb.append(root.val).append(SEPARATOR);

        serialize(root.left, sb);
        serialize(root.right, sb);
    }


    public static void main(String[] args) {
        TreeNode treeRoot = new TreeNode(1);
        treeRoot.left = new TreeNode(2);
        treeRoot.left.left = new TreeNode(3);
        treeRoot.left.right = new TreeNode(4);
        treeRoot.right = new TreeNode(5);
        treeRoot.right.right = new TreeNode(6);

        FlattenTree flattenTree = new FlattenTree();
//        flattenTree.flatten(treeRoot);
//        System.out.println("ok");
        System.out.println(flattenTree.serialize(treeRoot));
    }
}
